package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 使用DFS算法解决多点可达性问题：给定一副有向图和顶点的集合，
 * 回答是否存在一条从顶点集中的任意顶点到达给定顶点的有向路径。
 * 
 * @author 付大石
 *
 */
public class DirectedSearch {

    public static void main(String[] args) {
        
        DirectedGraph g = new DirectedGraph(13);
        g.addEdge(4,2);
        g.addEdge(2,3);
        g.addEdge(3,2);
        g.addEdge(6,0);
        g.addEdge(0,1);
        g.addEdge(2,0);
        g.addEdge(11,12);
        g.addEdge(12,9);
        g.addEdge(9,10);
        g.addEdge(9,11);
        g.addEdge(8,9);
        g.addEdge(10,12);
        g.addEdge(11,4);
        g.addEdge(4,3);
        g.addEdge(3,5);
        g.addEdge(7,8);
        g.addEdge(8,7);
        g.addEdge(5,4);
        g.addEdge(0,5);
        g.addEdge(6,4);
        g.addEdge(6,9);
        g.addEdge(7,6);
        System.out.println(g);
        
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list,1,2,6);
        DirectedSearch ds = new DirectedSearch(g,list);
        for(int i=0;i<g.v();i++) {
            if(ds.marked(i)) {
                System.out.println(i+"可达");
            }
        }
    }
    
    /**
     * 标记数组
     */
    private boolean marked[];

    public DirectedSearch(DirectedGraph g, int source) {
        marked = new boolean[g.v()];
        dfs(g, source);
    }

    public DirectedSearch(DirectedGraph g, Iterable<Integer> sources) {
        marked = new boolean[g.v()];
        for (int source : sources) {
            if (!marked[source]) {
                dfs(g, source);
            }
        }
    }

    /**
     * 深度优先遍历
     * @param graph
     * @param v
     */
    private void dfs(DirectedGraph g,int v) {
        
        marked[v] = true;
        for(int w : g.adj(v)) {
            if(!marked[w]) {
                dfs(g,w);
            }
        }
    }

    /**
     * 是否可到达v
     * @param v
     * @return
     */
    public boolean marked(int v) {
        return marked[v];
    }
}
